﻿#include<iostream>
#include<fstream>
#include<string.h>
#include<map>
#define SIZE 1000
#define MAXEDGE 5000
using namespace std;
int src_flow[SIZE][SIZE],src_cost[SIZE][SIZE],customer[SIZE][2];
int nodesize, linksize, customersize;
int servercost;
int allcost=0,need=0;
map<int,int> sever;
void read_in_file(string filename)
{
	cout<<"reading in "<<filename<<endl;
	ifstream fscr(filename.c_str(),ios::in);
	fscr>>nodesize>>linksize>>customersize>>servercost;
	for(int i=0;i<linksize;i++)
	{
		int from, to, cap, cost;
		fscr>>from>>to>>cap>>cost;
		src_flow[from][to]=cap;
		src_flow[to][from]=cap;
		src_cost[from][to]=cost;
		src_cost[to][from]=cost;
	}
	for(int i=0;i<customersize;i++)
	{
		int cus,node,need;
		fscr>>cus>>node>>need;
		customer[cus][0]=node;
		customer[cus][1]=need;
	}
	fscr.close();
}
int check(string filename)
{
	cout<<"checking "<<filename<<endl;
	int line,n;
	int path[MAXEDGE];
	ifstream frus(filename.c_str(),ios::in);
	frus>>line;
	for(int i=0;i<line;i++)
	{
		n=0;
		char c='x';
		while(c!='\n')
		{
			frus>>path[n++];
			frus.get(c);
		}
		if(sever.count(path[0])==0)
		{
			sever[path[0]]++;
			allcost+=servercost;
			cout<<"add sever at node:"<<path[0]<<endl;
		}
		for(int j=0;j<n-3;j++)
		{
			if(src_flow[path[j]][path[j+1]]==-1)
			{
				cout<<"at line :"<<i<<","<<"there is not a edge from node:"<<path[j]<<" to node:"<<path[j+1]<<endl;
				return 1;
			}
			src_flow[path[j]][path[j+1]]-=path[n-1];
			if(src_flow[path[j]][path[j+1]]<0)
			{
				cout<<"at line :"<<i<<","<<"there is not enough flow at edge: "<<path[j]<<" "<<path[j+1]<<endl;
				return 1;
			}
			allcost+=path[n-1]*src_cost[path[j]][path[j+1]];
		}
		if(customer[path[n-2]][0]!=path[n-3])
		{
			cout<<"at line :"<<i<<","<<"there is not a edge from customer node:"<<path[n-2]<<" to node:"<<path[n-3]<<endl;
			return 1;
		}
		customer[path[n-2]][1]-=path[n-1];
		need+=path[n-1];
		if(customer[path[n-2]][1]<0)
		{
			cout<<"at line :"<<i<<","<<"customer node:"<<path[n-2]<<" out of need"<<endl;
			return 1;
		}
	}
	for(int i=0;i<customersize;i++)
	{
		if(customer[i][1]>0)
		{
			cout<<"customer node:"<<i<<"don't get enough flow : "<<endl;
			return 1;
		}
	}
	frus.close();
	return 0;
}
int main(int argc,char *argv[])
{
	memset(src_flow,-1,SIZE*SIZE*sizeof(int));
	memset(src_cost,-1,SIZE*SIZE*sizeof(int));
	memset(customer,-1,SIZE*2*sizeof(int));
	if(argc==1)
	{
		read_in_file("case8.txt");
		check("topo8.txt");
	}
	else if(argc==3)
	{
		read_in_file(argv[1]);
		check(argv[2]);
	}
	cout<<"need:"<<need<<"   cost:"<<allcost<<endl;
	return 0;
} 
